A number of hardware and software techniques may be used to improve the execution speed of a software program. The time required to execute the program is dependent upon a number of factors including the number of instructions required to execute the program, the average number of processor cycles required to execute an instruction, and the processor cycle time.
Software scheduling of instructions can be used to enhance the program execution rate. This may be accomplished by using software to reorder the instructions so that they can be executed more efficiently. In other words, software scheduling helps to select the order of a sequence of instructions so that they execute correctly in a minimum amount of time within the constraints of the processor resource limitations.
One prior art software scheduling technique is known as basic block scheduling. Typically the program instructions are divided into code or instruction sequences called basic blocks. A program may consist of any number of basic blocks. A basic block has the property that if any instruction in the block is executed, then all other instructions within the basic block are executed. Thus, only the first instruction in the basic block can be a branch target or entry point. Similarly, only the last instruction in the basic block can be a branch instruction. This ensures that if any instruction in the code sequence is executed, then all instructions within the code sequence are executed. The technique of scheduling instructions or reordering the instructions within a basic block for optimal execution efficiency is called block scheduling.
The prior art technique of block scheduling suffers from the disadvantage that code optimization for each basic block may not result in overall optimal code. Basic block scheduling does not permit instructions to be moved across block boundaries such as branches. Thus although the execution time of each block may be nearly optimal, the overall program execution speed may not be optimal because the processor must hesitate at each branch (i.e., a basic block boundary) until all instructions preceding and including the branch are in execution.
Another class of prior art software scheduling techniques is specifically designed to improved the execution speed of program loops. A program loop is a sequence of instructions in which the last instruction is a branch instruction that may branch to the first instruction in the sequence under certain conditions. Thus the program loop might execute iteratively until some certain condition is met. Software pipelining is a technique used to improve processor throughput of a program loop.
Software pipelining effectively hides instruction latencies in a pipelined processor by overlapping the execution of different loop iterations of a loop structure in the program code. In other words, before one loop iteration completes, execution of successive iterations of the loop is initiated. The initiation interval is the number of processor cycles between the initiation of a given iteration and the initiation of the next iteration.
One disadvantage of prior art software pipelining techniques is that they are effective only for simple loop structures. In particular, some prior art software scheduling techniques are applicable only to a simple loop structure consisting of one basic block. Thus some prior art software pipelining methods are unable to handle more complicated loop structures such as nested loop structures or loops having more than one basic block.
Another disadvantage of some prior art software pipelining methods is that they only work for special hardware or for a narrow class of program loops.
What is needed is a software scheduling technique such as a software pipelining that is applicable to a broader class of instruction sequences including instruction sequences having one or more basic blocks. In particular, a method of software pipelining a sequence of instructions that have a single control flow entry and one or more control flow exits (i.e., a hyperblock program loop) is needed.